#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <sys/time.h>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) 
{
  vector< vector<int> > ret;
  if(nums.size()<3)
    return ret;

  std::sort( nums.begin(), nums.end() );

  if(nums[0]>0||nums.back()<0)
    return ret;

  for(int i=0;i<(nums.size()-2)&&nums[i]<=0;++i)
  {
    for(int j=i+1;j<(nums.size()-1);++j)
    {
      for(int k=(nums.size()-1);k>j&&(nums[k]>=0);--k )
      {
        if( (nums[i]+nums[j]+nums[k])==0 )
        {
          vector<int> a;
          a.push_back(nums[i]);
          a.push_back(nums[j]);
          a.push_back(nums[k]);
          ret.push_back( a );
        }
        while( nums[k]==nums[k-1] )
        {
          k--;
        }
      }

      while(nums[j]==nums[j+1])
      {
        j++;
      }
    }
    while(nums[i]==nums[i+1])
    {
      i++;
    }
  }

  return ret;

}



int main(int argc,char *argv[])
{

  vector<int> nums={-9,14,-7,-8,9,1,-10,-8,13,12,6,9,3,-3,-15,-15,1,8,-7,-4,-6,8,2,-10,8,11,-15,3,0,-11,-1,-1,10,0,6,5,-14,3,12,-15,-7,-5,9,11,-1,1,3,-15,-5,11,-12,-4,-4,-2,-6,-10,-6,-6,0,2,-9,14,-14,-14,-9,-1,-2,-7,-12,-13,-15,-4,-3,1,14,3,-12,3,3,-10,-9,-1,-7,3,12,-6,0,13,4,-15,0,2,6,1,3,13,8,-13,13,11,11,13,14,-6};


  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  vector< vector<int> > ret = threeSum( nums );


  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
       <<"leetcode server time consuming should less than 500ms"<<endl
       << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  for(int i=0;i<ret.size();++i)
  {
    for(int j=0;j<ret[0].size();++j)
    {
      cout<<ret[i][j]<<",";
    }
    cout<<endl;
  }


  return 0;
}
